1. Technical Field
The present invention relates generally to improved memory storage for data processing systems, and in particular, but not exclusively, to an apparatus and method for detecting multiple hits in a Content Addressable Memory (CAM) array.
2. Description of Related Art
CAM, or associative memory, is a special type of memory storage device typically used for high speed searching applications. Each CAM device includes comparison logic, so that the contents of the bit positions can be compared within the device. In standard computer memory devices (e.g., DRAMs, SRAMs, etc.), their bits are addressed by memory location, and the contents of their bits are conveyed to an Arithmetic Logic Unit (ALU) outside of the memory device for comparison purposes.
A data word can be input to a CAM device, and the CAM device can search its entire memory for the input word. If the CAM device finds the word in its memory, the device returns a list with the storage address(es) of the memory location(s) where the word was found. As such, a CAM device can perform such a search of its entire memory in one operation. Consequently, a CAM device is significantly faster than a RAM device for most search applications.
All words that are input (e.g., entries) to a CAM device can be compared to the words stored in the device. However, at most, only one word stored in the device should match the entry. Nevertheless, a significant problem with existing CAM devices is that a circuit failure or software error external to the CAM device can cause the occurrence of so-called “multiple hits”. If a multiple hit condition exists, multiple word-lines are enabled in the CAM device and erroneous outputs are returned. In such a case, it is important to be able to detect a multiple hit condition in a CAM device before such erroneous outputs can be returned. However, existing techniques for detecting multiple hit conditions in CAM devices incur substantial penalties in terms of space, because a relatively large number of gates are required to tap all of the word-lines in the device in order to determine if more than one word-line is enabled or turned on.
Therefore, it would be advantageous to have an apparatus and method for detecting multiple hit conditions in CAM devices that, at a minimum, do not incur substantial penalties in terms of space.